原始题目：剑指 Offer 65. 不用加减乘除做加法 (opens new window)

解题思路：

本题考察的是通过位运算来做加法。

加法需要考虑进位，在位运算里，进位可以通过左移然后加回无进位和中。

假设有两个数的二进制形式 $a$ 和 $b$。其和 $s = a + b$。对于第 $i$ 位来说，$a(i$) 和 $b(i)$ 相加可能有以下的结果。

$a(i)$	$b(i)$	无进位和 $n(i)$	进位 $c(i+1)$
$0$	$0$	$0$	$0$
$1$	$0$	$1$	$0$
$0$	$1$	$1$	$0$
$1$	$1$	$0$	$1$

观察可以看出，$n(i)$ 是 $a(i)$ 和 $b(i)$ 异或的结果，而 $c(i+1)$ 是 $a(i)$ 和 $b(i)$ 与运算然后左移一位的结果。

$$\begin{cases} n = a ⊕ b \\ c = (a \& b ) << 1 \end{cases}$$

因此，求 $s$ 的过程转化成求 $a$ 和 $b$ 的无进位和 $n$ 以及进位 $c$ 的过程，然后将 $c$ 补还给 $n$。补还之后，可能会产生新的进位，因此需要循环处理，直到进位为 $0$。

$$s = a + b → n + c$$

这个过程同样适合与 $a$ 或者 $b$ 为负数的时候，因为正数负数都是用补码存储的。

代码：

public int add(int a, int b) {
    while (b != 0) {
        // 求进位
        int c = (a & b) << 1;
        // 不考虑进位，结果赋值给 a
        a = a ^ b;
        // 如果存在进位，则 b != 0，那么在下一个循环中，
        // 就会将进位和 a 相加，直到进位为 0
        b = c;
    }
    return a;
}

复杂度分析

• 时间复杂度$O(1)$：最差情况下（例如 $a$ = 0x7fffffff​ , $b = 1$ 时），需循环 $32$ 次，使用 $O(1)$ 时间；每轮中的常数次位操作使用 $O(1)$ 时间。
• 空间复杂度$O(1)$：辅助变量占用常数大小的空间。